package com.cctc.juc.source.Bitc.Icontainer.hash;

import javax.swing.tree.TreeNode;
import java.util.AbstractMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * [HashMap 哈希（散列）字典]
 * 要求：熟练掌握（手撕、陈述）HashMap [哈希（散列）字典] 核心（主干）实现逻辑。
 * 概述：HashMap 是一个基于 Node 数组构建的哈希表，Node 作为 HashMap 中的一个内部类，由关键字 key，关键字 key 的散列值，节点元素值 value，以及 next 后继节点组成。
 * HashMap 基于哈希函数计算出关键字 key 的散列值，然后定位到目标节点在 Node 数组中的位置（下标），以此达到数据访问的目的。
 * HashMap 使用的哈希函数采用的是数位分析算法实现的，关键字 key 的哈希值为一个 int 类型 32 位的整数，HashMap 将其一分为二，高 16 位不变，整体右移 16 位，将低 16 位与高 16 位进行异或，作为关键字 key 的哈希值，然后再使用低位与 Node 数组长度进行逻辑与运算，定位到目标节点在 Node 数组中的位置（下标），从而使所有节点元素均匀分布在 Node 数组中不同的哈希槽内，减少哈希冲突，提升 HashMap 的整体读写效率。
 * 另外，在 HashMap 内部有几个重要的属性，例如 loadFactor、threshold 等，用于动态调整哈希表（Node 数组）的容量，HashMap 中 Node 数组的默认初始容量为 16，加载因子为 0.75f，二者相乘得到默认的初始扩容阈值为 12，即当 Node 数组中的节点数量首次达到 12 时，将会调用 resize() 方法，执行扩容操作，空间大了，哈希冲突的概率也就小了，目的还是为了提升 HashMap 的整体读写效率。
 * 但是，再完美的哈希算法也避免不了哈希冲突，当出现哈希冲突时，HashMap 采用链地址法将出现冲突的节点链接在一起建立一个单向链表，查询时间复杂度变为 O(n [链表长度])。为了提升查找效率，当链表长度（链表节点数量） n 达到 8 且数组大小（总节点数量）达到 64 时，将会触发树化操作，HashMap 会将链表转化为红黑树，以此提升查找效率；此外，当红黑树节点数量减少到 6 时，二者查询性能相差不大，为了提升写性能效率，又会触发反树化操作，HashMap 会将红黑树再次转化为单向链表，以此达到时空平衡。
 */
public class AHMap_AAAAA<K, V> extends AbstractMap<K, V> implements Map<K, V> {
    /**
     * [Node 数据节点（数据模型）] 内部类。
     * - 单向链表，只有 next 后继节点；
     * - 关键字 key 和节点值 value 都可以为 null，即允许 null 节点存在。
     */
    static class Node<K, V> implements Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) return true;
            if (o instanceof Entry) {
                Entry e = (Entry) o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) {
                    return true;
                }
            }
            return false;
        }
    }

    // --- [核心属性] --- //
    // Node 节点（哈希槽）数组，其中每个 Node（头）节点又是一个单向链表，用于存放哈希冲突的 Node 数据节点。
    transient Node<K, V>[] table;
    /**
     * 扩容参数：
     * - size，为实际存储 Node 数据节点的数量；
     * - threshold = capacity（容量，初始为 16）* loadFactor（加载因子，初始为 0.75）；
     * 一旦 size > threshold，将会触发 resize 扩容操作。
     */
    transient int size;
    // 加载因子，初始为 0.75
    final float loadFactor;
    // 扩容阈值，初始为（16 * 0.75）12
    int threshold;
    /**
     * MVCC 并发写版本号（乐观锁），禁止在遍历（读）时进行并发写（插入、删除等）操作，避免出现幻读问题。
     * - 只允许通过 HashIterator 迭代器的 remove() 删除方法进行删除操作。
     */
    transient int modCount;
    // 初始容量，最大容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4, MAXINUM_CAPACITY = 1 << 30;
    // 初始负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 树化（链表 -> 红黑树）参数：
     * - 当链表节点达到树化阈值（8）& 数组容量（64）时，将触发树化（链表 -> 红黑树）操作；
     * - 当红黑树节点低于反树化阈值（6）时，将触发反树化（红黑树 -> 链表）操作。
     */
    static final int TREEIFY_THRESHOLD = 8, MIN_TREEIFY_CAPACITY = 64, UNTREEIFT_THRESHOLD = 6;

    // --- [核心构造器] --- //

    public AHMap_AAAAA(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) throw new IllegalArgumentException();
        if (initialCapacity > MAXINUM_CAPACITY) initialCapacity = MAXINUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException();
        this.loadFactor = loadFactor;
        /**
         * 这里将数组容量（capacity）赋值给了 threshold 进行临时保存。
         * 因为没有显式定义 capacity 属性，且 table 数组是延时初始化的。
         * 当首次调用 put() 方法时，table 数组会取这个 threshold 临时值（或使用 DEFAULT_INITIAL_CAPACITY 常量）进行初始化，然后再计算 threshold = capacity * loadFacor 覆盖初始 threshold 值。
         */
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 计算大于等于给定值的最小的 2 的幂作为数组（初始、扩容）容量。
     * 计算过程：通过累加 5 次无符号右移运算得到大于等于给定值的最小的 2 的幂。
     * 例如 n = 10（1010）- 1 = 1001，减 1 的目的是另外找到的目标值大于或等于原值，主要是为了避免给定值本身就是 2 的幂时，计算结果为给定值的 2 倍的情况：
     * - n |= n >>> 1：1001 | 0100 = 1101；
     * - n |= n >>> 2：1101 | 0011 = 1111；
     * - n |= n >>> 4：1111 | 0000 = 1111；
     * ... ...
     * 最后返回 n + 1 = 1111 + 1 = 10000 = 16，即为大于等于 10 的最小的 2 的幂。
     */
    static final int tableSizeFor(int capacity) {
        int n = capacity - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n < 0 ? 1 : n >= MAXINUM_CAPACITY ? MAXINUM_CAPACITY : n + 1;
    }

    // --- [核心方法] --- //

    /**
     * 计算关键字 key 的哈希值，用于定位数组下标（哈希槽 = hash & [n - 1]）。
     * 哈希算法：关键字 key 的哈希码高 16 位不变，低 16 位与高 16 位进行异或（充分利用关键字 key 的每一位），作为键 key 的哈希值。
     * 即取 int 类型的一半，刚好可以将该二进制数对半切开，再异或（同 0 异 1）打散，减少哈希冲突。
     * 然后使用打散的哈希值，定位 table 数组的下标（哈希槽）= hash & [n - 1]。
     * 即 table 数组的下标只与（打散的）哈希值的低 n 位有关，散列性较好，冲突较低。
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >> 16);
    }

    /**
     * 写操作。
     */
    @Override
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * 写（插入 | 更新）操作。
     * 核心逻辑：
     * 1）如果 table 数组还未初始化，调用 resize() 方法，执行 table 数组初始化操作；
     * 2）基于关键字 key 的散列值，定位目标节点在 table 数组中的位置（下标），获取根节点；
     * 3）如果根节点不存在，则创建，作为新插入节点，直接走 6）；
     * 4）如果根节点存在，尝试获取目标更新节点：
     * 4.1）如果目标节点存在，且刚好是根节点，则获取目标节点；
     * 4.2）如果根节点是红黑树节点，调用 putTreeVal() 方法，执行红黑树写操作，获取目标节点；
     * 4.3）否则，遍历链表，继续尝试获取目标更新节点：
     * - 如果目标节点不存在，则创建一个新节点插入到链表尾部，作为新插入节点，直接走 6）；
     * --> 如果插入新节点后，链表长度（Node 节点数量）达到了树化阈值（TREEIFY_THRESHOLD [8]），则调用 treeifyBin() 方法，将链表转化成红黑树，提升读写效率；
     * - 否则，获取目标更新节点；
     * 5）更新目标节点的 value 值，维护 LinkedHashMap 的节点访问次序，更新操作结束，返回旧元素值；
     * 6）维护写版本号；
     * 7）如果数组大小（Node 节点数量）超过了扩容阈值，调用 resize() 方法，执行扩容操作；
     * 8）维护 LinkedHashMap 子类的节点插入次序；
     * 9）插入操作结束，返回 null；
     *
     * @param hash         关键字 key 的哈希码
     * @param key          关键字
     * @param value        元素值
     * @param onlyIfAbsent 如是否只有在元素值不存在时才执行写（插入）操作？即是否只插入新节点不更新旧节点元素的只？
     * @param evict        在 LinkedHashMap 子类执行完插入操作后，是否驱逐最近未被访问的节点元素？
     * @return 如果是插入操作，返回 null；如果是更新操作，返回旧元素值。
     */
    private V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K, V>[] tab;
        int n;
        int index;
        Node<K, V> parent;
        // 1）如果 table 数组尚未初始化，则使用 resize() 方法进行初始化；
        if ((tab = table) == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }
        // 2）使用键 key 的哈希值定位 table 数组下标（哈希槽）
        // 3）如果顶层父节点不存在，则创建，然后直接走 6）；
        if ((parent = tab[index = (n - 1) & hash]) == null) {
            tab[index] = new Node<>(hash, key, value, null);
        } else {
            // 4）否则，获取目标节点：
            Node<K, V> target;
            K k;
            // 4.1）如果目标节点已存在，且刚好是顶层父节点，则直接获取目标节点，走 5）；
            if (parent.hash == hash && ((k = parent.key) == key || (key != null && key.equals(k)))) {
                target = parent;
            }
            // 4.2）如果顶层父节点是红黑树节点，则调用 putTreeVal() 方法，执行红黑树的写操作，然后返回目标节点，走 5）；
            else if (parent instanceof TreeNode) {
                target = ((TreeNode<K, V>) parent).putTreeVal(this, tab, hash, key, value);
            }
            // 4.3）否则，从链表中寻找目标更新节点：
            else {
                for (int binCount = 0; ; binCount++) {
                    // - 如果目标节点不存在，则新建节点，插入到链表尾部，直接走 6）；
                    if ((target = parent.next) == null) {
                        parent.next = new Node<>(hash, key, value, null);
                        // --> 如果插入新节点之后，链表节点达到树化阈值（8），调用 treeifyBin() 方法，执行树化操作，将链表转化成红黑树，提高读写性能。
                        if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
                        break;
                    }
                    // - 否则，获取目标更新节点，走 5）；
                    if (target.hash == hash && (k = target.key) == key || (key != null && key.equals(k))) {
                        break;
                    }
                    parent = target;
                }
            }
            // 5）更新目标节点的 value 值，维护 LinkedHashMap 子类的节点访问次序，返回旧 value 值；
            if (target != null) {
                V oldValue = target.value;
                if (!onlyIfAbsent || oldValue == null) target.value = value;
                afterNodeAccess(target);
                return oldValue;
            }
        }
        // 6）维护写版本号；
        modCount++;
        // 7）如果数组大小（Node 节点数量）超过了扩容阈值（threshold），使用 resize() 方法进行扩容；
        if (++size > threshold) resize();
        // 8）维护 LinkedHashMap 子类的节点插入次序；
        afterNodeInsertion(evict);
        // 9）结束，返回。
        return null;
    }

    /**
     * 扩容操作。
     * 核心逻辑：
     * 1）如果 table 数组尚未初始化，初始化 table 数组并更新扩容阈值（threshold = initialCapacity [16] * loadFactor [0.75f] = 12）；
     * 2）否则，判断数组大小（Node 节点数量）是否超过扩容阈值？
     * - 如果没有，直接返回原 table 数组；
     * - 否则，走 3）；
     * 3）将 table 数组容量扩充到原来的 2 倍，并更新扩容阈值（threshold = initialCapacity [32] * loadFactor [0.75f] = 24）；
     * 4）正序遍历 table 数组，迁移数据（Node 节点）到新 table 数组内：
     * 4.1）如果只有一个根节点，基于关键字 key 的哈希值重新定位（hash & [nn - 1]）目标节点在新 table 数组中的位置（下标）；
     * 4.2）如果根节点存在后继节点，判断根节点的类型：
     * - 如果根节点是红黑树节点，前序遍历红黑树节点，基于关键字 key 的哈希值重新定位（hash & [nn - 1]）目标节点在新 table 数组中的位置（下标）；
     * - 如果根节点是链表节点，正序遍历链表节点，基于关键字 key 的哈希值重新定位（hash & [nn - 1]）目标节点在新 table 数组中的位置（下标）；
     * 5）迁移完毕，返回新 table 数组。
     * 说明：JDK 7 中没有引入红黑树，扩容操作是从链表尾部倒序遍历的，而 JDK 8 中的链表或红黑树是采用正序或前序遍历的，没有改变原有的顺序。
     */
    final Node<K, V>[] resize() {
        // ... 省略（掌握核心实现逻辑 [伪代码] 即可） ...
        return new Node[0];
    }


    /**
     * 读操作。
     */
    @Override
    public V get(Object key) {
        Node<K, V> node;
        return (node = getNode(hash(key), key)) == null ? null : node.value;
    }

    /**
     * 读操作。
     * 核心逻辑：
     * 1）基于关键字 key 的散列值，定位到目标节点在 table 数组中的位置（下标），获取根节点，查找目标节点；
     * 1.1）如果目标节点刚好是根节点，直接返回结果；
     * 1.2）如果根节点的后继节点存在：
     * - 如果根节点是红黑树节点，调用 getTreeNode() 方法，从红黑树中查找目标节点，返回结果；
     * - 否则，遍历链表查找目标节点。
     *
     * @param hash 关键字 key 的散列值；
     * @param key  关键字
     * @return 元素值。
     */
    final Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab;
        int n;
        K k;
        Node<K, V> parent, target;
        // 1）使用键 key 的哈希值定位 table 数组下标（哈希槽），拿到顶层父节点（parent = table[hash & (n - 1)]），获取目标节点。
        if ((tab = table) != null && (n = tab.length) > 0 && (parent = tab[hash & (n - 1)]) != null) {
            // 1.1）如果目标节点刚好是顶层父节点，直接返回结果；
            if (parent.hash == hash && ((k = parent.key) == key || (key != null && key.equals(k)))) {
                return parent;
            }
            // 1.2）如果顶层父节点的后继节点不为空：
            if ((target = parent.next) != null) {
                // - 如果顶层父节点是红黑树节点，则执行 getTreeNode() 方法，从红黑树中获取目标节点；
                if (parent instanceof TreeNode) {
                    return ((TreeNode<K, V>) parent).getTreeNode(hash, key);
                }
                // - 否则，遍历链表寻找目标节点。
                do {
                    if (target.hash == hash && ((k = target.key) == key || (key != null && key.equals(k)))) {
                        return target;
                    }
                } while ((target = target.next) != null);
            }
        }
        return null;
    }

    /**
     * 删除操作。
     */
    @Override
    public V remove(Object key) {
        Node<K, V> node;
        return (node = removeNode(hash(key), key, null, false, true)) == null ? null : node.value;
    }

    /**
     * 删除操作。
     * 核心逻辑：
     * 1）基于关键字 key 的散列值，定位目标节点在 table 数组中的位置（下标），拿到根节点，查找目标删除节点；
     * 1.1）如果目标节点刚好是根节点，则直接获取目标节点；
     * 1.2）如果根节点的后继节点存在：
     * - 如果根节点是红黑树节点，则调用 getTreeNode() 方法，从红黑树中查找目标节点；
     * - 否则，遍历链表查找目标节点；
     * 2）删除目标节点：
     * 2.1）如果目标节点是红黑树节点，则调用 removeTreeNode() 方法，从红黑树中删除目标节点；
     * 2.2）如果目标节点是根节点，则直接删除根节点；
     * 2.3）否则，从链表中删除目标节点；
     * 3）维护写操作版本号；
     * 4）更新数组大小；
     * 5）维护 LinkedHashMap 子类的节点删除次序；
     * 6）返回删除节点。
     *
     * @param hash       关键字 key 的哈希值
     * @param key        关键字
     * @param value      元素值
     * @param matchValue 是否需要匹配到元素值后再执行删除操作？
     * @param movable    如果删除的是红黑树节点，删除之后是否需要移动节点其他？
     * @return 删除节点。
     */
    private Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
        Node<K, V>[] tab;
        int n;
        int index;
        Node<K, V> parent;
        // 1）使用键 key 的哈希值定位 table 数组下标（哈希槽），拿到顶层父节点（parent = table[hash & (n - 1)]），寻找目标（删除）节点。
        if ((tab = table) != null && (n = tab.length) > 0 && (parent = tab[index = (hash & (n - 1))]) != null) {
            Node<K, V> target = null, next;
            K k;
            V v;
            // 1.1）如果目标节点刚好是顶层父节点，则直接获取目标节点；
            if (parent.hash == hash && ((k = parent.key) == key || (key != null && key.equals(k)))) {
                target = parent;
            }
            //  1.2）如果顶层父节点的后继节点不为空，寻找目标节点：
            else if ((next = parent.next) != null) {
                // - 如果顶层父节点是红黑树节点，则执行 getTreeNode() 方法，从红黑树中获取目标节点；
                if (parent instanceof TreeNode) target = ((TreeNode<K, V>) parent).getTreeNode(hash, key);
                    // - 否则，遍历链表寻找目标节点。
                else {
                    do {
                        if (next.hash == hash && (k = next.key) == key || (key != null && key.equals(k))) {
                            target = next;
                            break;
                        }
                        parent = next;
                    } while ((next = next.next) != null);
                }
            }
            // 2）删除目标节点：
            if (target != null && (!matchValue || (v = target.value) == value || (value != null && value.equals(v)))) {
                // 2.1）如果目标节点是红黑树节点，则执行 removeTreeNode() 方法，从红黑树中删除目标节点；
                if (target instanceof TreeNode) {
                    ((TreeNode<K, V>) target).removeTreeNode(this, tab, movable);
                }
                // 2.2）如果目标节点是顶层父节点，直接删除顶层父节点；
                else if (target == parent) tab[index] = target.next;
                    // 2.3）否则，删除目标节点；
                else parent.next = target.next;
                // 3）维护写版本号；
                modCount++;
                // 4）更新数组大小（Node 节点数量）；
                size--;
                // 5）维护 LinkedHashMap 子类的节点访问次序；
                afterNodeRemoval(target);
                // 6）返回删除节点。
                return target;
            }
        }
        return null;
    }


    /**
     * 以下三个方法是为 LinkedHashMap 子类定义的钩子函数，用于维护节点次序，实现不同的缓存策略。
     * - afterNodeAccess：在访问元素之后，将该元素移到双向链表的尾部。
     * - afterNodeInsertion：在插入新元素之后，判断是否（true）需要移除最近未被访问（LRU）的元素！我们可以通过覆写 LinkedHashMap 的 removeEldestEntry 抽象方法实现不同的缓存策略。
     * - afterNodeRemoval：在删除元素之后，将该元素从双向链表中移除。
     */

    void afterNodeAccess(Node<K, V> p) {
    }

    void afterNodeInsertion(boolean evict) {
    }

    void afterNodeRemoval(Node<K, V> p) {
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

}
